package test;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

/**
 * @author dx
 * @version 1.0
 * @date 2022/5/20 10:14
 * @description:  重建二叉树
 */
class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x){this.val = x;}
}


public class BuildTree {
    public static void main(String[] args) {
        int []preorder = {3,9,20,15,7};
        int []inorder = {9,3,15,20,7};
        TreeNode ans = new BuildTree_Solution().build(preorder,inorder);
        previsrt(ans);
    }
    public static void previsrt(TreeNode node){
        if(node == null){
            return;
        }
        System.out.println(node.val);
        previsrt(node.left);
        previsrt(node.right);
    }
}


class BuildTree_Solution{
    Map<Integer,Integer> map = new HashMap<Integer,Integer>();
    public TreeNode build(int[] preorder,int[] inorder){

        for(int i =0;i<inorder.length;i++){
            map.put(inorder[i],i);
        }
        //创建的树的根节点
        TreeNode root =  mybuild(preorder,0,inorder.length-1,0);;
        return root;
    }

    //preorder_left : 前序遍历的左边界  preorder_right:前序遍历的右边界 inorder_left:中序遍历的左边界,inorder_left为了求左子树的个数
    public TreeNode mybuild(int[] preorder,int preorder_left,int preorder_right,int inorder_left){

        if(preorder_left > preorder_right){
            return null;
        }
        TreeNode root = new TreeNode(preorder[preorder_left]);
        int index = map.get(preorder[preorder_left]); //得到中序遍历中根节点的位置
        int left_size = index - inorder_left; //得到左子树的个数 也就拿到了左子树的范围

        //递归构造左子树 ：给出左子树范围，构造左子树的时候 inorder_left不用变
        root.left =  mybuild(preorder,preorder_left+1,preorder_left+left_size,inorder_left);
        //递归构造右子树 : 给出右子树的范围，构造右子树的时候 inorder_left是上一次中间节点(根节点)的+1,
        root.right = mybuild(preorder,preorder_left+left_size+1,preorder_right,index+1);
        return root;
    }
}
